/* 
    !想象老式火车
    大多数编程语言
        如果数组容量不够,需要扩容

    链表优势
        :内存空间不是必须连续的,可以实现灵活的内存动态管理
        :每一个元素由一个存储 *元素本身的节点* 和一个 *指向下一个元素的引用* 组成
        :链表在插入和删除数据时,时间复杂度可以达到O(1),相对数组效率高很多
    链表缺点
        :链表访问任何一个元素,都需要从头开始访问
        :无法通过下标直接访问元素,需要从头一个个访问,直到找到对应的元素
*/

function LinkedList() {
  // 节点类   next传不传都能接受
  function Node(data) {
    this.data = data;
    this.next = null;
  }

  // 默认指向null
  this.head = null;
  // 记录链表长度
  this.length = 0;

  // *追加方法
  LinkedList.prototype.append = function (data) {
    // 1.创建新节点
    let newNode = new Node(data);
    // 2.判断添加的数据是否是第一个节点
    if (this.length === 0) {
      this.head = newNode;
    }
    // 3.不是第一个节点
    else {
      let current = this.head;
      // 通过循环找到最后一个节点(next指向null则为最后的节点)
      while (current.next) {
        current = current.next;
      }
      // 让最后节点的next指向新节点
      current.next = newNode;
    }
    // 链表长度++
    this.length++;
  };

  // *toString方法
  LinkedList.prototype.toString = function () {
    // 1.定义变量
    let current = this.head;
    let listString = '';
    // 2.通过循环获取节点
    while (current) {
      listString += current.data + ' ';
      // !避免循环
      current = current.next;
    }
    return listString;
  };

  // *insert方法
  LinkedList.prototype.insert = (position, data) => {
    // 1.判断position越界
    if (position < 0 || position > this.length) return false;

    // 2.创建新节点
    let newNode = new Node(data);

    // 3.判断插入的位置是否是第一个
    if (position === 0) {
      // 新节点的指针指向第一个节点
      newNode.next = this.head;
      // head指针指向新节点
      this.head = newNode;
    }
    // 4.插入的位置不是第一个
    else {
      let index = 0;
      let current = this.head; // #存储当前节点的后一个节点信息
      let previous = null; // #存储当前节点的前一个节点信息
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      newNode.next = current; // #新节点的next指向后一个节点
      previous.next = newNode; // #[当前节点的前一个节点]指向新节点
    }

    // 5.插入成功后
    this.length++;
    return true;
  };

  // *get方法
  LinkedList.prototype.get = (position) => {
    // 1.越界判断
    if (position < 0 || position >= this.length) return null;

    // 2.获取对应的数据
    let current = this.head;
    let index = 0;

    while (index++ < position) {
      current = current.next;
    }

    // 3.跳出循环后返回对应位置的数据
    return current.data;
  };

  // *indexOf方法
  LinkedList.prototype.indexOf = (data) => {
    // 1.定义变量
    let current = this.head;
    let index = 0;

    // 2.进行查找
    while (current) {
      if (current.data === data) return index;
      index++;
      current = current.next;
    }

    // 3.找到最后没有找到
    return -1;
  };

  // *update 修改某个位置的元素
  LinkedList.prototype.update = (position, newData) => {
    // 1.越界判断
    if (position < 0 || position >= this.length) return false;

    // 2.查找正确的节点
    let index = 0;
    let current = this.head;

    while (index++ < position) {
      current = current.next;
    }

    // 3.将position位置的data修改为newData
    current.data = newData;
    return true;
  };

  // *removeAt 删除链表中的特定元素
  LinkedList.prototype.removeAt = (position) => {
    // 1.越界判断
    if (position < 0 || position >= this.length) return null;

    // 2.判断删除的节点是第一个
    let current = this.head; // #存储当前节点的后一个节点信息3

    if (position === 0) {
      this.head = this.head.next;
    }
    // 删除的节点不是第一个
    else {
      let index = 0;
      // let current = this.head;
      let previous = null; // #存储当前节点的前一个节点信息
      while (index++ < position) {
        previous = current;
        current = current.next;
      }
      // 前一个的指针指向当前指针的后一个指针
      previous.next = current.next;
    }

    // 3.更新链表长度
    this.length--;
    return current.data;
  };

  // *remove  根据元素删除节点
  LinkedList.prototype.remove = (data) => {
    // 1.获取data在链表中的位置
    let position = this.indexOf(data);

    // 2.根据位置信息,删除节点
    return this.removeAt(position);
  };

  LinkedList.prototype.isEmpty = () => {
    return this.length === 0;
  };

  LinkedList.prototype.size = () => {
    return this.length;
  };
}

// class写法
/* class LinkedList {
  constructor() {
    this.data = data;
    this.next = next;
    // 默认指向null
    this.head = null;
    // 记录链表长度
    this.length = 0;
  }
}
 */

let list = new LinkedList();
list.append('cool');
list.append('a');
list.append('b');
list.append('c');
list.insert(0, '第一人称');
list.insert(5, 'last');
console.log('indexOf查a', list.indexOf('a'));
console.log('indexOf查b', list.indexOf('b'));
console.log('indexOf查c', list.indexOf('c'));
console.log(list.get(5));
console.log(list.toString());
console.log('更新后的list', list.update(2, '这是更改后的第二个数据'));
console.log(list.toString());
console.log(list.removeAt(0));
console.log(list.remove('c'));
console.log(list.toString());
